1. Field of the Invention
The present invention relates to a signal compression method which is suitable for representing an enormous signal sequence with a small amount of information, to a device, to a program and to a recording medium. The present invention also relates to a signal retrieval method which, along with utilizing the signal compression method, is suitable for finding out the position of a signal which is similar to a signal which has been registered in advance from among an enormous signal sequence, to a device, to a program, and to a recording medium.
2. Description of Related Art
In the past, as signal retrieval methods for finding a position of a signal within a colossal signal sequence which is similar to a signal which has been inputted, there have been proposed several per se known high speed signal retrieval methods which find at high speed a position in a similar signal; for example, Japanese Patent 3,065,314 (Patent Reference #1), and Japanese Unexamined Patent Application, First Publication No. 2001-092486 (Patent Reference #2).
Furthermore, with regard to the above described type of signal retrieval method, as a method which reduces the cost of calculation for matching features one at a time by performing feature compression of the signal, there have been proposed methods for reducing the dimensions of the features in an effective manner (for example, Non-Patent Reference #3, specified below) by piecewise linear mapping which takes advantage of the continuity of a time series signal. These methods create mapping by segmenting a signal evenly into equal segments regardless of the properties of the signal. Furthermore, it is per se known to vary the length of the segments according to the properties of the signal (for example, see Non-Patent Reference #1: E. Keogh, K. Chakrabarti, S. Mehrotra, and M. Pazzani, “Locally adaptive dimensionality reduction for indexing large time series databases”, Proc. of ACM SIGMOD Conference, pp. 151-162, 2001; or Non-Patent Reference #2: C. Wang and S. Wang, “Supporting content-based searches on time series via approximation”, Proc. of International Conference on Scientific and Statistical Database Management (SSDBM2000), pp. 69-81, 2000).
Furthermore, in the above type of signal retrieval method, as a method for locally eliminating matching procedures which are not required, there is a per se known time series active search method in which the lower limit value of the distance is calculated in advance of matching by taking advantage of the properties of the histograms which are the features utilized for matching, and matching procedures are eliminated insofar as that a threshold which has been decided upon in advance is not exceeded; for example, see Patent Reference #1: Japanese Patent 3,065,314, and Patent Reference #2: Japanese Unexamined Patent Application, First Publication No. 2001-092486.
Furthermore, as a technique for signal compression which is utilized in the above kind of signal retrieval method, there is a per se known signal compression method which can retain feature sequences with a small memory capacity and can perform decisions relating to similarity between signals at high speed by reducing the dimensions of feature sequences which have been extracted from an audio signal. This signal compression technique is utilized in the above described signal retrieval method for finding out the position from among a signal sequence of a signal which is similar to another signal which has been registered in advance, such as when detecting the instant during a broadcast audio signal at which a specified tune has been played, or the like, and it is capable of being executed at high speed. In connection with the concrete signal compression methods which are used for such a technique, there are per se known signal compression methods for segmenting and compressing an original signal which has been provided in advance; for example, see Non-Patent Reference #3: “A Quick Search Method for Video Signals Based on Piecewise Linear Maps” by Akisato Kimura and three others, Technical Report of IEICE, The Institute of Electronics, Information and Communication Engineers, February 2002, Vol. 101, No. 653, pp. 75-80.
Here, with the high speed signal retrieval methods of the above described Patent Reference #1 and Patent Reference #2, for an absolutely colossal signal sequence, there may be a problem that it is not possible to find a similar signal within a sufficiently short time period, and there is a problem that it is not possible to deal with features other than histograms.
Furthermore, with a signal compression method such as described in the above Non-Patent Reference #1 or Non-Patent Reference #2, it has become possible to perform signal compression at higher compression ratios than heretofore, there is the problem that a colossal amount of processing is required for determining the most suitable method of signal division.
Yet further, with a signal compression method such as described in the above Non-Patent Reference #3, although the sub-signal may be built up by segmenting the original signal evenly and equally regardless of the properties of that signal, alternatively, it is also possible to vary the length of the segments according to the properties of the signal. Accordingly, it has become possible to perform signal compression at better compression ratios than heretofore, with this method, there is the problem that a colossal amount of processing has become necessary for determining the function for performing compression.